package datastruct;

import java.util.Deque;
import java.util.LinkedList;

public class DailyTemperatures {

    /**
     * LeetCode T739 每日温度
     * 总结：使用单调栈
     * @param args
     */
    public static void main(String[] args) {
        DailyTemperatures main = new DailyTemperatures();
        main.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73});
    }

    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Deque<Node> deque = new LinkedList<>();
        deque.push(new Node(0, temperatures[0]));
        for (int i = 1; i < temperatures.length; i++){
            while (!deque.isEmpty()){
                Node node = deque.peek();
                if (node.temperature < temperatures[i]){
                    deque.pop();
                    res[node.index] = i - node.index;
                } else {
                    break;
                }
            }
            deque.push(new Node(i, temperatures[i]));
        }

        return res;
    }
    class Node {
        int index;
        int temperature;
        Node(int index, int temperature){
            this.index = index;
            this.temperature = temperature;
        }
    }
}
